import java.util.Arrays;
public class TestHeap {
    public int[] elem;
    public int usesize;
    public TestHeap(){
        this.elem=new int[10];
    }
    public void insert(int[] array){
        for (int i = 0; i <array.length ; i++) {
            elem[i]=array[i];//将元素插入到一个新数组里
            usesize++;//统计元组个数
        }
    }
    //创建大根堆//parent从最左侧的最大堆调整
    public void createHeap(){
        for (int parent = (usesize-1-1)/2; parent>=0 ; parent--) {
            shiftdown(parent,usesize);
        }

    }
    public void shiftdown(int parent,int usesize){
        int child=2*parent+1;
        while (child<usesize){
            if(child+1<usesize&&elem[child]<elem[child+1]){
                child++;//结束条件是不存在左右子树，if中的内容判断左右子树的大小
            }
            if(elem[child]>elem[parent]){
                swap(elem,child,parent);
                parent=child;
                child=2*parent+1;
            }
            else {
                break;
            }
        }
    }
    public void swap(int[] elem,int i,int j){
        int tmp=elem[i];
        elem[i]=elem[j];
        elem[j]=tmp;
    }
    public int poll(){
        if(isEmpty()){
            return -1;
        }
        int ret=elem[0];
        swap(elem,0,usesize);
        usesize--;
        shiftdown(0,usesize-1);
        return ret;
    }
    public boolean isEmpty(){
        return  usesize==0;
    }
    public void offer(int val){
        if(isFull()){
            elem=Arrays.copyOf(elem,2*elem.length);
        }
        elem[usesize]=val;
        usesize++;
        shiftup(usesize-1);
    }

    public boolean isFull(){
        return usesize==elem.length;
    }
    public void shiftup(int child){
        int parent=(child-1)/2;
        while (child>0){
            if(elem[child]>elem[parent]){
                swap(elem,child,parent);
                child=parent;
                parent=(child-1)/2;
            }
            else {
                break;
            }
        }
    }

}
